package likou.tanxin;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/10/08 08:51
 */
public class _435 {
    public static void main(String[] args) {
        System.out.println(eraseOverlapIntervals(new int[][]{{1,2}, {2,3}, {3,4}, {1,3},{2,2} }));
    }
    // 前到后

    private static int eraseOverlapIntervals(int[][] intervals) {

        Arrays.sort(intervals,new Comparator<int[]>(){
            @Override
            public int compare(int a[], int b[]){
                if(a[0]==b[0]){
                    return a[1]-b[1];
                }
                return a[0]-b[0];
            }
        });

        if(intervals.length==0) {
            return 0;
        }
        int count=0,pre=0,i,len=intervals.length;
        for(i=1;i<len;i++){
            //如果前一个的尾大于后一个的头，就++
            if(intervals[pre][1]>intervals[i][0]){
                count++;
                //包含关系，前面包含后面，就直接把去掉前面的，因为当前的更小
                if(intervals[pre][1]>intervals[i][1]) {
                    pre=i;
                }
            }
            else{
                pre=i;
            }
        }
        return count;
    }
}
